package com.gwcloud.leetcode.tags.backtrace;

/** 
* @ClassName   : Leetcode306 
* @author      : ganwei 
* @date        : 2020年5月11日 
* @Description : leetcode 306. 累加数 
*/
public class Leetcode0306 {
	
	/**
	 * -回溯大法继续发挥
	 */
    public boolean isAdditiveNumber(String num) {
    	return backtrack(num,num.length(),0,0,0,0);
    }
    
    /**
     * -回溯主体
     * @param num    原始字符串
     * @param len    原始字符串长度
     * @param start  当前处理下标
     * @param sum    前面的两个数字之和
     * @param pre    前一个数字
     * @param k      当前是处理的第几个数字
     */
    public boolean backtrack(String num, int len, int start, long sum, long pre, int k) {
    	if(start == len) {
    		return k > 2;
    	}
    	
    	for(int i = start; i < len; i++) {
    		long cur = fetchCurValue(num, start, i);
    		//无效数字
    		if(cur < 0) {
    			continue;
    		}
    		//剪枝：当前数字不等于前面两数之和
    		if(k >= 2 && cur != sum) {
    			continue;
    		}
    		
    		if(backtrack(num,len,i+1,pre+cur,cur,k+1)) {
    			return true;
    		}
    		
    		
    	}
    	return false;
    }
    
    /**
     * -判断有效数字
     */
    public long fetchCurValue(String num, int l, int r) {
        if (l < r && num.charAt(l) == '0') {
            return -1;
        }
        
        long res;
        try {
        	res = Long.valueOf(num.substring(l, r+1));
        }catch(NumberFormatException e) {
        	return -1;
        }

        return res;	
    }
    
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0306 l306 = new Leetcode0306();
    	
    	System.out.println(l306.isAdditiveNumber("11235813213455890144"));
    	System.out.println(Long.valueOf("1234"));
    }
}
